package class06;

public class TraversalBinaryTree {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int v) {
			value = v;
		}
	}

	public static void f(Node head) {
		if (head == null) {
			return;
		}
		// 1
		f(head.left);
		// 2
		f(head.right);
		// 3
	}

	//序表示头所在的位置
	/**
	     1
	   2   3
	 4  5 6  7

	 1 2 4 5 3 6 7
	 递归序: 1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1
	 */
	//先序: 头 左 右 (每一颗)
	// 先序打印所有节点
	public static void pre(Node head) {
		//实际是利用了递归序(遍历每个节点的顺序)
		//递归序: 1 2 2 2 1 3 3 3 1
		//先序 -> 第一个1就打印(第一个2就打印, 第一个3就打印...)
		//中序 -> 第一个1就打印
		//后序 -> 第一个1就打印

		/*
		     1
		   2   3
		 f(1) -> f(2) -> f(null 左) -> f(2) -> f(null 右)  -> f(2) -> f(1)
		 f(1) -> f(3) -> f(null 左) -> f(3) -> f(null 右)  -> f(3) -> f(1)
		 */
		//到了头节点
		if (head == null) {
			return;
		}
		//第一次回到头结点
		//第一次就打印 -> 先序遍历
		System.out.println(head.value);
		pre(head.left);
		//执行完后第二次回到头节点
		pre(head.right);
		//执行完后第三次回到头结点
	}

	/**
	     1
	   2   3
	 4  5 6  7

	 4 2 5 1 6 3 7
	 */
	//中序: 左 头 右 (每一颗)
	public static void in(Node head) {
		if (head == null) {
			return;
		}
		in(head.left);
		//递归序第二次打印
		System.out.println(head.value);
		in(head.right);
	}

	/**
	     1
	   2   3
	 4  5 6  7

	 4 5 3 6 7 3 1
	 */
	//后序: 左 右 头 (每一颗)
	public static void pos(Node head) {
		if (head == null) {
			return;
		}
		pos(head.left);
		pos(head.right);
		//递归序第三次打印
		System.out.println(head.value);
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		pre(head);
		System.out.println("========");
		in(head);
		System.out.println("========");
		pos(head);
		System.out.println("========");

	}

}
